public class Test {
    // 二分查找
    public int search(int[] nums, int t) {
        int left = 0,right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;// 防溢出 2^32
            if(nums[mid] < t) left = mid + 1;
            else if(nums[mid] > t) right = mid - 1;
            else return mid;
    }
        return -1;
}

// 朴素二分查找模板
    /*
    while(left <= right)
    {
            int mid = left + (right - left) / 2;// 防溢出 2^32
            if(...)
                left = mid + 1;
            else if(...)
                right = mid - 1;
            else
                return ...;
    }
     */

    public int[] searchRange(int[] nums, int t) {
        int[] ret = {-1,-1};
        if(nums.length == 0){
            return ret;
        }
        int left = 0,right = nums.length - 1;
        //求区间的左端点
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= t) right = mid;
            else left = mid + 1;
        }
        if(nums[left] == t) ret[0] = left;
        else return ret;
        //求区间的右端点
        left = 0;// 没有必要让left = 0
        right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= t) left = mid;
            else right = mid - 1;
        }
        if(nums[right] == t) ret[1] = right;
        else return new int[]{-1,-1};
        return ret;
    }

    //总结二分模板
    /*
    // 查找区间左端点的模板
    while(left < right)
    {
    int mid = left + (right - left) / 2;
    if(...) left = mid + 1;
    else right = mid;
    }
    // 查找区间右端点的模板
    while(left < right)
    {
    int mid = left + (right - left + 1) / 2;
    if(...) left = mid;
    else right = mid - 1;
    }

    // 记忆技巧 : 当下面呢出现-1的时候 上面就+1
     */


    //x的平方根
    public int mySqrt(int x) {
        if(x < 1) return 0;
        long left = 1,right = x;
        while(left < right){
            long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;// 注意数据范围
            else right = mid - 1;
        }
        return (int)left;//强转一下
    }

    //搜索插入位置
    public int searchInsert(int[] nums, int t) {
        int n = nums.length - 1;
        if(nums[n] < t) return nums.length;//特殊情况判断
        int left = 0,right =n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= t) right = mid;
            else left = mid + 1;
        }
        return right;
    }

    //山峰数组的峰顶索引
    public int peakIndexInMountainArray(int[] arr) {
        int left = 1,right = arr.length - 2;//细节处理 因为一定不会是数组的第一个和最后一个元素
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] > arr[mid - 1]) left = mid;
            else right = mid - 1;//代码优化
        }
        return left;
    }

    //寻找峰值
    public int findPeakElement(int[] nums) {
        int left = 0,right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid + 1]) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    //寻找旋转排序数组中的最小值
    public int findMin(int[] nums) {
        int n = nums.length - 1;//以最后的值为目标值
        int left = 0,right = n,target = nums[n];
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > target) left = mid + 1;
            else right = mid;
        }
        return nums[left];

    }

    // 点名
    public int takeAttendance(int[] records) {
        int left = 0, right = records.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        // 处理细节
        return left == records[left] ? left + 1 : left;
    }

}
